package JzOffer.jz42;

import java.util.ArrayList;

/**
 * @author 张取
 * @version 1.0
 * @date 2022/1/9 下午1:05
 * JzOffer.jz42
 */

public class Solution03 {
    public static void main(String[] args){
        RecentCounter03 recentCounter = new RecentCounter03();
        System.out.println(recentCounter.ping(1));
        System.out.println(recentCounter.ping(100));
        System.out.println(recentCounter.ping(3001));
        System.out.println(recentCounter.ping(3002));
    }
}

class RecentCounter03 {

    private ArrayList<Integer> times;
    private final int windowSize;
    /** left可以让二分查找的起始边界不从0开始 */
    private int left;

    public RecentCounter03(){
        times = new ArrayList<>();
        windowSize = 3000;
        left = 0;
    }

    /** 有bug */
    public int ping(int t){
        times.add(t);
        if(t < windowSize){
            return times.size();
        }
        int right = times.size() - 1;
        int mid = 0;
        //范围[t-windowSize, t],查找最后一次小于或等于t-windowSize的位置
        while(left <= right){
            mid = (right - left) / 2 + left;
            if(times.get(mid) < (t - windowSize)){
                left = mid + 1;
            } else if(times.get(mid) > (t - windowSize)){
                right = mid - 1;
            } else {
                break;
            }
        }

        if(times.get(mid) == (t-windowSize)){
            return times.size() - mid;
        } else {
            //mid为最后一次小于t-windowSize的位置
            return times.size() - mid - 1;
        }
    }
}
